/*!
\file AlgPrim.cpp
\brief Contains implementation of AlgPrim.
\ingroup Plugins
*/

#include"AlgPrim.h" 

AlgPrim::AlgPrim( Graph *g ): Algorithm( g ){
	containerAdd();
}

AlgPrim::~AlgPrim(){
	
}

void AlgPrim::run(){
	Container &cont = container(0);
	cont.push_back( (new ContainerElement)->setNode(graph()->node(0)) );
	bool success = true;
	int n = graph()->numNodes();
	bool *seen = new bool[n];
	for( int i = 0; i < n; i++ )
		seen[i] = false;
	seen[0] = true;
	
	while( success ){
		success = false;
		int i = -1;
		int min = -1;
		for( int j = 0; j < graph()->numEdges(); j++ ){
			const Edge &e = graph()->edge(j);
			
			//If we found at least one eligible edge and this one has higher weight, skip it.
			if( success && e.label().toInt() >= min )
				continue;
			
			if( seen[e.from().identifier()] && !seen[e.to().identifier()] ){
				success = true;
				min = e.label().toInt();
				i = j;
				
			}else if( seen[e.to().identifier()] && !seen[e.from().identifier()] ){
				success = true;
				min = e.label().toInt();
				i = j;
			}
		}
		
		if( success ){
			const Edge &e = graph()->edge(i);
			if( seen[e.from().identifier()] ){
				cont.push_back( (new ContainerElement)->setNode(e.to())->setEdge(e) );
				seen[e.to().identifier()] = true;
			}else{
				cont.push_back( (new ContainerElement)->setNode(e.from())->setEdge(e) );
				seen[e.from().identifier()] = true;
			}
		}
	}
	
	for( int i = 0; i < graph()->numEdges(); i++ ){
		const Edge &e = graph()->edge(i);
		bool shouldKeep = false;
		for( int j = 1; j < cont.size() && !shouldKeep; j++ )
			shouldKeep = e == *cont[j]->edge();
		if(!shouldKeep){
			graph()->removeEdge(e);
			i--;
			printf("Removing Edge from %d (%s) to %d (%s)\n", e.from().identifier(), e.from().label().toAscii().data(), e.to().identifier(), e.to().label().toAscii().data());
		}
	}
}
 
